class Solution:
    def nthUglyNumber(self, n: int) -> int:
        dp = [0 for _ in range(n+1)]
        dp[1] = 1
        p1=1
        p2=1
        p3=1
        for i in range(2, n+1):  
            num1 = dp[p1]*2
            num2 = dp[p2]*3
            num3 = dp[p3]*5
            dp[i] = min(num1, min(num2, num3))
            if(dp[i]==num1):p1+=1
            if(dp[i]==num2):p2+=1
            if(dp[i]==num3):p3+=1
        return dp[n]